package DynamicProgramming;

public class 回文子串 {
    public int countSubstrings(String s) {
        //动态规划
         /*int len = s.length();
         boolean[][] dp = new boolean[len][len];
         int count = 0;
         for (int i = len - 1; i >= 0; i--) {
             for (int j = i; j < len; j++) {
                 if (s.charAt(i) == s.charAt(j)) {
                     if (j - i <= 1 || dp[i + 1][j - 1]) {
                         dp[i][j] = true;
                         count++;
                     }
                 }
             }
         }
         return count;*/

        //中心扩散
        int len = s.length();
        int count = 0;
        for (int i = 0; i < 2 * len - 1; i++) {
            int left = i / 2, right = left + i % 2;
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                count++;
                left--;
                right++;
            }
        }
        return count;
    }
}
